package com.graph;

import com.tgy.heap.BinaryHeap;
import com.tgy.heap.Visitor;
import com.unionfind.GenericUnionFind;

import java.util.*;

/**
 *  邻接表
 * @Author: tgy
 * @Date: 2020-10-22 09:49
 */
public class AdjacencyListGraph<V,E> extends AbstractGraph<V,E>{

   private static class Vertex<V,E>{

       V value;
       /**
        * 从当前节点出去的边
        */
       Set<Edge<V,E>> outEdges;
       /**
        * 到达当前节点的边
        */
       Set<Edge<V,E>> inEdges;

       public Vertex(V value) {

           this.value = value;

           outEdges = new HashSet<>();
           inEdges = new HashSet<>();
       }

       @Override
       public boolean equals(Object o) {

           if (this == o) {
               return true;
           }
           if (!(o instanceof Vertex)) {
               return false;
           }

           Vertex<?, ?> vertex = (Vertex<?, ?>) o;
           return value != null ? value.equals(vertex.value) : vertex.value == null;
       }

       @Override
       public int hashCode() {

           return value != null ? value.hashCode() : 0;
       }

       @Override
       public String toString() {
           return "Vertex{" +
                   "value=" + value +
                   ", outEdges=" + outEdges +
                   ", inEdges=" + inEdges +
                   '}';
       }
   }

   private static class Edge<V,E> {

       Vertex<V,E> from;
       Vertex<V,E> to;
       E weight;

       public Edge(Vertex<V,E> from, Vertex<V,E> to) {

           this(from,to,null);
       }

       public Edge(Vertex<V,E> from, Vertex<V,E> to, E weight) {
           this.from = from;
           this.to = to;
           this.weight = weight;
       }

       @Override
       public boolean equals(Object o) {
           if (this == o) {
               return true;
           }
           if (!(o instanceof Edge)) {
               return false;
           }

           Edge<?, ?> edge = (Edge<?, ?>) o;

           if (from != null ? !from.equals(edge.from) : edge.from != null) {
               return false;
           }
           return to != null ? to.equals(edge.to) : edge.to == null;
       }

       @Override
       public int hashCode() {
           int result = from != null ? from.hashCode() : 0;
           result = 31 * result + (to != null ? to.hashCode() : 0);
           return result;
       }

       @Override
       public String toString() {

           StringBuilder sb = new StringBuilder();

           sb.append("Edge{ from=").append(from.value);
           sb.append(", to=").append(to.value);
           if (Objects.nonNull(weight)) {

               sb.append(", weight=").append(weight);
           }
           sb.append(" }");

           return sb.toString();
       }

       protected EdgeInfo<V,E> toEdgeInfo() {

           return new EdgeInfo<>(from.value,to.value,weight);
       }
   }

   private HashMap<V,Vertex<V,E>> vertices = new HashMap<>();

   private int edgesSize;

    public AdjacencyListGraph() {

        this(null);
    }

    public AdjacencyListGraph(Operations<E> operations) {
        super(operations);
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        vertices.forEach((V v,Vertex<V,E> vertex)->{

            sb.append(vertex).append("\n");
        });

        return sb.toString();
    }

    @Override
    public int verticesSize() {

        return vertices.size();
    }

    @Override
    public int edgesSize() {

        return edgesSize;
    }

    @Override
    public void addVertex(V v) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.nonNull(vertex)) {

            return;
        }
        vertices.put(v,new Vertex<>(v));
    }


    @Override
    public void addEdge(V from, V to) {

        addEdge(from,to,null);
    }

    @Override
    public void bfs(V v, Traversal<V> traversal) {

        Vertex<V, E> vertex = vertices.get(v);
        if (Objects.isNull(vertex)) {

            return;
        }


        HashSet<Vertex<V, E>> visitors = new HashSet<>();

        Queue<Vertex<V, E>> queue = new LinkedList<>();
        queue.offer(vertex);
        visitors.add(vertex);
        while (!queue.isEmpty()) {

            vertex = queue.poll();

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (visitors.contains(outEdge.to)) {

                    continue;
                }

                queue.offer(outEdge.to);
                visitors.add(outEdge.to);
            }

            if (Objects.nonNull(traversal) && traversal.visitor(vertex.value)) {

                break;
            }
        }
    }
    @Override
    public void dfs(V v,Traversal<V> traversal) {

        if (Objects.isNull(traversal)) {

            return;
        }

        dfs03(v,traversal);
//        recursionDFS(vertex,vistors,traversal);
    }

//    @Override
    public void dfs01(V v,Traversal<V> traversal) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex)) {

            return;
        }

        Stack<Vertex<V, E>> stack = new Stack<>();

        HashSet<Vertex<V, E>> vistors = new HashSet<>();

        stack.push(vertex);
        vistors.add(vertex);

        while (!stack.empty()) {

            vertex = stack.pop();

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (vistors.contains(outEdge.to)) {

                    continue;
                }

                stack.add(outEdge.to);
                vistors.add(outEdge.to);
            }

            if (Objects.nonNull(traversal) && traversal.visitor(vertex.value)) {

                break;
            }
        }
    }

    public void dfs02(V v,Traversal<V> traversal) {

        if (Objects.isNull(traversal)) {

            return;
        }

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex)) {

            return;
        }

        Stack<Vertex<V, E>> stack = new Stack<>();

        HashSet<Vertex<V, E>> vistors = new HashSet<>();

        stack.push(vertex);

        while (!stack.empty()) {

            vertex = stack.pop();

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (vistors.contains(outEdge.to)) {

                    continue;
                }

                stack.add(outEdge.from);
                stack.add(outEdge.to);
                break;
            }

            if (vistors.contains(vertex)) {

                continue;
            }

            vistors.add(vertex);
            if (traversal.visitor(vertex.value)) {

                break;
            }
        }
    }


    public void dfs03(V v,Traversal<V> traversal) {

        if (Objects.isNull(traversal)) {

            return;
        }

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex)) {

            return;
        }

        Stack<Vertex<V, E>> stack = new Stack<>();

        HashSet<Vertex<V, E>> vistors = new HashSet<>();

        stack.push(vertex);
        vistors.add(vertex);

        if (traversal.visitor(vertex.value)) {

            return;
        }

        while (!stack.empty()) {

            vertex = stack.pop();

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (vistors.contains(outEdge.to)) {

                    continue;
                }

                stack.add(outEdge.from);
                stack.add(outEdge.to);
                vistors.add(outEdge.to);

                if (traversal.visitor(outEdge.to.value)) {
                    return;
                }

                break;
            }
        }
    }



    @Override
    public void addEdge(V from, V to, E weight) {

        /**
         * 添加节点
         */
        addVertex(from);
        addVertex(to);

        Vertex<V, E> vertexFrom = vertices.get(from);
        Vertex<V, E> vertexTo = vertices.get(to);

        Edge<V, E> edge = new Edge<>(vertexFrom, vertexTo, weight);

        if (vertexFrom.outEdges.remove(edge)) {

            vertexTo.inEdges.remove(edge);
        }else {

            edgesSize++;
        }

        vertexFrom.outEdges.add(edge);
        vertexTo.inEdges.add(edge);
    }

    @Override
    public void removeVertex(V v) {

        Vertex<V, E> vertex = vertices.get(v);


        if (Objects.isNull(vertex)) {

            /**
             * 不存在的节点
             */
            return;
        }

        for (Edge<V, E> outEdge : vertex.outEdges) {

            outEdge.to.inEdges.remove(outEdge);
            edgesSize--;
        }

        for (Edge<V, E> inEdge : vertex.inEdges) {

            inEdge.from.outEdges.remove(inEdge);
            edgesSize--;
        }

        vertices.remove(v);
    }


    @Override
    public void removeEdge(V from, V to) {

        Vertex<V, E> vertexFrom = vertices.get(from);
        Vertex<V, E> vertexTo = vertices.get(to);

        if (Objects.isNull(vertexFrom) || Objects.isNull(vertexTo)) {

            return;
        }

        Edge<V, E> edge = new Edge<V, E>(vertexFrom, vertices.get(to), null);

        vertexFrom.outEdges.remove(edge);
        vertexTo.inEdges.remove(edge);
        edgesSize--;
    }

    /**
     * 拓扑排序
     * @return
     */
    @Override
    public List<V> topologicalsort() {

        ArrayList<V> sort = new ArrayList<>();

        if (vertices.size() == 0) {

            return sort;
        }

        HashMap<Vertex<V,E>,Integer> inEdgesCounts = new HashMap<>();
        Queue<Vertex<V,E>> queue = new LinkedList<>();

        vertices.forEach((v,vertice)->{

            if (vertice.inEdges.size() == 0) {

                queue.offer(vertice);
            }else {

                inEdgesCounts.put(vertice,vertice.inEdges.size());
            }
        });


        while (!queue.isEmpty()) {

            Vertex<V, E> vertex = queue.poll();

            sort.add(vertex.value);

            for (Edge<V, E> outEdge : vertex.outEdges) {

                Integer count = inEdgesCounts.get(outEdge.to);

                if (count == 0) {

                    continue;
                }
                inEdgesCounts.put(outEdge.to,--count);

                if (count == 0) {

                    queue.add(outEdge.to);
                }
            }

        }

        return sort;
    }

    @Override
    public Set<EdgeInfo<V, E>> minimumSpanningTree() {

        HashSet<EdgeInfo<V, E>> mstEdges = new HashSet<>();
        if (vertices.size() == 0) {

            return mstEdges;
        }

//        prim(mstEdges);
        kruskal(mstEdges);
        return mstEdges;
    }

    @Override
    public Map<V, ShortestPath<V, E>> customShortestPath(V v) {

        Map<V, ShortestPath<V, E>> selectPaths = new HashMap<>();
        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex) || vertices.size() == 1) {

            return selectPaths;
        }

        Map<Vertex<V,E>, ShortestPath<V, E>> paths = new HashMap<>();

        for (;;) {

            for (Edge<V, E> outEdge : vertex.outEdges) {

                if (outEdge.to.value.equals(v) || selectPaths.keySet().contains(outEdge.to.value)) {
                    continue;
                }

                ShortestPath<V, E> shortestPath = paths.get(outEdge.to);

                if (Objects.isNull(shortestPath)) {
                    // 第一次加入paths map中
                    shortestPath = new ShortestPath<>();
                    paths.put(outEdge.to,shortestPath);
                }

                E oldWeigth = shortestPath.getPathLength();
                E newWeigth =outEdge.weight;

                ShortestPath<V, E> path = selectPaths.get(vertex.value);

                if (Objects.nonNull(path)) {

                    newWeigth = operations.add(selectPaths.get(vertex.value).getPathLength(), newWeigth);
                }

                if (Objects.nonNull(oldWeigth) && operations.cpm(newWeigth,oldWeigth) >= 0) {

                    continue;
                }

                shortestPath.setPathLength(newWeigth);
                shortestPath.getPaths().clear();

                if (vertex.value.equals(v)) {

                    shortestPath.getPaths().add(v);
                }

                if (Objects.nonNull(path) && path.getPaths().size() > 0) {

                    shortestPath.getPaths().addAll(path.getPaths());
                }

                shortestPath.getPaths().add(outEdge.to.value);
            }

            // 查找 paths里面最小到path
            Map.Entry<Vertex<V, E>, ShortestPath<V, E>> shortestPathEntry = minPath(paths);
            vertex = shortestPathEntry.getKey();
            selectPaths.put(vertex.value,shortestPathEntry.getValue());

            paths.remove(vertex);

            if (paths.size() == 0) {

                break;
            }


        }

        return selectPaths;
    }

    @Override
    public Map<V, PathInfos<V, E>> shortestPath(V v) {

        if (vertices.size() <= 1) {

            return null;
        }

//        return dijkstra(v);
        return bellmanFord(v);
    }


    @Override
    public Map<V, Map<V, PathInfos<V, E>>> allShortestPath() {


        Map<V, Map<V, PathInfos<V, E>>> allPaths = new HashMap<>();

        for (Map.Entry<V, Vertex<V, E>> vVertexEntry : vertices.entrySet()) {

            V v = vVertexEntry.getKey();
            Map<V, PathInfos<V, E>> pathInfosMap = allPaths.get(v);

            if (Objects.isNull(pathInfosMap)) {

                pathInfosMap = new HashMap<>();
                allPaths.put(v,pathInfosMap);
            }

            for (Edge<V, E> outEdge : vVertexEntry.getValue().outEdges) {

                PathInfos<V, E> pathInfos = new PathInfos<>(outEdge.weight);
                pathInfos.getPaths().add(outEdge.toEdgeInfo());
                pathInfosMap.put(outEdge.to.value,pathInfos);
            }
        }


        for (V k : vertices.keySet()) {

            for (V i : vertices.keySet()) {

                for (V j : vertices.keySet()) {

                    if (k.equals(i) || i.equals(j) || j.equals(k)) {

                        continue;
                    }

                    PathInfos<V, E> ikPathInfo = getPathInfos(i,k,allPaths);

                    if (Objects.isNull(ikPathInfo)) {
                        continue;
                    }

                    PathInfos<V, E> kjPathInfo = getPathInfos(k,j,allPaths);

                    if (Objects.isNull(kjPathInfo)) {

                        continue;
                    }

                    PathInfos<V, E> ijPathInfo = getPathInfos(i,j,allPaths);

                    E newWeight = operations.add(ikPathInfo.getWeight(), kjPathInfo.getWeight());
                    if (Objects.nonNull(ijPathInfo) && compare(ijPathInfo.getWeight(),newWeight) <= 0) {

                        continue;
                    }

                    if (Objects.isNull(ijPathInfo)) {

                        ijPathInfo = new PathInfos<>(operations.zero());
                        allPaths.get(i).put(j,ijPathInfo);
                    }else {

                        ijPathInfo.getPaths().clear();
                    }

                    ijPathInfo.setWeight(newWeight);
                    ijPathInfo.getPaths().addAll(ikPathInfo.getPaths());
                    ijPathInfo.getPaths().addAll(kjPathInfo.getPaths());
                }

            }

        }

        return allPaths;
    }

    private PathInfos<V,E> getPathInfos(V v1,V v2,Map<V, Map<V, PathInfos<V, E>>> allPaths) {

        if (Objects.isNull(allPaths)) {

            return null;
        }

       return Objects.isNull(allPaths.get(v1))? null:allPaths.get(v1).get(v2);
    }

    /**
     * 最短路径 bellmanFord算法
     * @param v
     * @return
     */
    private Map<V,PathInfos<V,E>> bellmanFord(V v) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex)) {

            return null;
        }

        // 获取所有边的集合
        HashSet<Edge<V, E>> allEdge = new HashSet<>();
        for (Vertex<V, E> value : vertices.values()) {

            allEdge.addAll(value.outEdges);
        }

        HashMap<V, PathInfos<V, E>> paths = new HashMap<>();
        PathInfos<V, E> pathInfos = new PathInfos<>();
        pathInfos.setWeight(operations.zero());
        paths.put(v,pathInfos);


        for (int i = 0; i < vertices.size() - 1; i++) {

            boolean flag = false;
            for (Edge<V, E> veEdge : allEdge) {
                pathInfos = paths.get(veEdge.from.value);
                // 如果没有到from的边，直接下一轮
                if (Objects.isNull(pathInfos)) {
                    continue;
                }
                if (ralax(paths,veEdge,pathInfos)) {

                    flag = true;
                }
            }

            if (!flag) {
                break;
            }
        }

        for (Edge<V, E> veEdge : allEdge) {

            pathInfos = paths.get(veEdge.from.value);
            // 如果没有到from的边，直接下一轮
            if (Objects.isNull(pathInfos)) {
                continue;
            }
            // 有负权环
            if (ralax(paths,veEdge,pathInfos)) {

                return null;
            }
        }

        return paths;
    }


    /**
     * 最短路径 dijkstra 算法
     * @param v 起始定点
     * @return
     */
    private Map<V,PathInfos<V,E>> dijkstra(V v) {

        Vertex<V, E> vertex = vertices.get(v);

        if (Objects.isNull(vertex)) {

            return null;
        }

        Map<V,PathInfos<V,E>> selectPaths = new HashMap<>(10);
        Map<V, PathInfos<V,E>> paths = new HashMap<>(10);

        for (Edge<V, E> outEdge : vertex.outEdges) {

            PathInfos<V, E> pathInfos = new PathInfos<>();
            pathInfos.setWeight(outEdge.weight);
            pathInfos.getPaths().add(outEdge.toEdgeInfo());
            paths.put(outEdge.to.value,pathInfos);
        }

        while (!paths.isEmpty()) {

            V minV = minPathInfo(paths);
            PathInfos<V, E> selectPathInfos = paths.get(minV);
            selectPaths.put(minV,selectPathInfos);
            paths.remove(minV);
            vertex = vertices.get(minV);
            for (Edge<V, E> outEdge : vertex.outEdges) {
                // 如果待松弛节点已经选中的，直接跳过
                if (selectPaths.keySet().contains(outEdge.to.value) || v.equals(outEdge.to.value)) {

                    continue;
                }
                ralax(paths,outEdge,selectPathInfos);
            }

        }

        return selectPaths;

    }

    /**
     * 松弛边
     * @param paths
     * @param outEdge
     * @param selectPathInfos
     */
    private boolean ralax(Map<V, PathInfos<V,E>> paths,Edge<V, E> outEdge,PathInfos<V, E> selectPathInfos ) {

        // 找一下之前有没有到 outEdge.to 的路径
        PathInfos<V, E> pathInfos = paths.get(outEdge.to.value);

        E newWeight = operations.add(selectPathInfos.getWeight(), outEdge.weight);


        if (Objects.nonNull(pathInfos) && compare(newWeight,pathInfos.getWeight()) > 0) {
            return false;
        }

        if (Objects.isNull(pathInfos)) {
            // 没有，创建
            pathInfos = new PathInfos<>();
            paths.put(outEdge.to.value,pathInfos);
        }else {

            pathInfos.getPaths().clear();
        }

        pathInfos.setWeight(newWeight);
        pathInfos.getPaths().addAll(selectPathInfos.getPaths());
        pathInfos.getPaths().add(outEdge.toEdgeInfo());
        return true;
    }


    private V minPathInfo(Map<V, PathInfos<V,E>> paths) {

        Iterator<Map.Entry<V, PathInfos<V, E>>> iterator = paths.entrySet().iterator();

        Map.Entry<V, PathInfos<V, E>> minPath = iterator.next();

        while (iterator.hasNext()) {

            Map.Entry<V, PathInfos<V, E>> next = iterator.next();

            if (compare(next.getValue().getWeight(),minPath.getValue().getWeight()) < 0) {

                minPath = next;
            }
        }

        return minPath.getKey();
    }

    /**
     * 获取最短路径
     * @param paths
     * @return
     */
    private Map.Entry<Vertex<V, E>, ShortestPath<V, E>> minPath(Map<Vertex<V,E>, ShortestPath<V, E>> paths) {

        Iterator<Map.Entry<Vertex<V, E>, ShortestPath<V, E>>> iterator = paths.entrySet().iterator();

        Map.Entry<Vertex<V, E>, ShortestPath<V, E>> min = iterator.next();

        while (iterator.hasNext()) {

            Map.Entry<Vertex<V, E>, ShortestPath<V, E>> next = iterator.next();
            if (compare(next.getValue().pathLength,min.getValue().pathLength) < 0) {

                min = next;
            }
        }

        return min;
    }


    /**
     * prim算法的最小生成树
     * @param mstEdges
     */
    private void prim(Set<EdgeInfo<V, E>> mstEdges) {

        Vertex<V, E> firstVertex = vertices.values().iterator().next();

        HashSet<Vertex<V, E>> vistors = new HashSet<>();

        AbstractGraph<V,E> _this = this;
        BinaryHeap<Edge<V, E>> edgeHeap = new BinaryHeap<>(new Comparator<Edge<V, E>>() {
            @Override
            public int compare(Edge<V, E> o1, Edge<V, E> o2) {

              return _this.compare(o2.weight,o1.weight);
            }
        },firstVertex.outEdges.toArray(new Edge[0]));

        vistors.add(firstVertex);
        Edge<V,E> veEdge = null;

        while (!edgeHeap.isEmpty() && mstEdges.size() < vertices.size() - 1) {

            veEdge = edgeHeap.remove();

            if (!vistors.contains(veEdge.to)) {

                mstEdges.add(veEdge.toEdgeInfo());
                vistors.add(veEdge.to);
            }

            for (Edge<V, E> outEdge : veEdge.to.outEdges) {

                if (vistors.contains(outEdge.to)) {
                    continue;
                }

                edgeHeap.add(outEdge);
            }
        }
    }

    /**
     * kruskal 最小生成树
     * @param mstEdges
     */
    private void kruskal(Set<EdgeInfo<V, E>> mstEdges) {

        AbstractGraph<V,E> _this = this;

        Set<Edge<V,E>> allEdge = new HashSet<>();

        vertices.forEach((v,vertices)->{

            allEdge.addAll(vertices.outEdges);
        });

        BinaryHeap<Edge<V, E>> edgeHeap = new BinaryHeap<>(new Comparator<Edge<V, E>>() {
            @Override
            public int compare(Edge<V, E> o1, Edge<V, E> o2) {

                return _this.compare(o1.weight,o2.weight);
            }
        },allEdge.toArray(new Edge[0]));

        GenericUnionFind<Vertex<V, E>> unionFind = new GenericUnionFind<>();

        for (Vertex<V, E> value : vertices.values()) {

            unionFind.addNode(value);
        }


        Edge<V, E> veEdge = null;

        while (!edgeHeap.isEmpty() && mstEdges.size() < vertices.size() - 1) {

            /**
             * 获取最小边
             */
            veEdge = edgeHeap.remove();

            // 判断是否在同一个集合中，避免出现环
            if (unionFind.isSame(veEdge.from,veEdge.to)) {

                continue;
            }

            mstEdges.add(veEdge.toEdgeInfo());
            unionFind.union(veEdge.from,veEdge.to);
        }

    }

    /**
     * 递归的深度优先
     * @param vertex
     * @param visitors
     * @param traversal
     */
    private void recursionDFS(Vertex<V,E> vertex,Set<Vertex<V,E>> visitors, Traversal<V> traversal) {

        visitors.add(vertex);
        if (Objects.nonNull(traversal) && traversal.visitor(vertex.value)) {

            traversal.stop = true;
            return;
        }

        for (Edge<V, E> outEdge : vertex.outEdges) {

            if (visitors.contains(outEdge.to)) {
                continue;
            }

            recursionDFS(outEdge.to,visitors,traversal);

            if (traversal.stop) {

                return;
            }
        }
    }
}
